package Text8;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    //    第一行包含两个正整数 n,m，表示天数和订单的数量。
//    第二行包含 n个正整数，其中第 i个数为 ri，表示第 i天可用于租借的教室数量。
//    接下来有 m行，每行包含三个正整数 dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。
//    每行相邻的两个数之间均用一个空格隔开。
//    天数与订单均用从 1开始的整数编号。
    static int N = 1000010, n, m;
    static int[] r = new int[N];
    static int[] d = new int[N];
    static int[] s = new int[N];
    static int[] t = new int[N];
    static long[] b = new long[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 1; i <= n; i++) {
            r[i] = in.nextInt();
        }
        for (int i = 1; i <= m; i++) {
            d[i] = in.nextInt();
            s[i] = in.nextInt();
            t[i] = in.nextInt();
        }
        if (check(m)) {
            System.out.println(0);
            return;
        }
        int l = 0, r = m;
        while (l < r) {
            int mid = l + r >> 1;
            if (!check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(-1);
        System.out.println(r);
    }

    private static boolean check(int mid) {
        Arrays.fill(b, 0);
        for (int i = 1; i <= mid; i++) {
            b[s[i]] += d[i];
            b[t[i] + 1] -= d[i];
        }
        for (int i = 1; i <= n; i++) {
            b[i] += b[i - 1];
            if (b[i] > r[i]) {
                return false;
            }
        }
        return true;
    }
}